package quickSort;

/**
 * Created by xupeng20 on 2019/2/14.
 * 快排第一步 以某个值进行划分 为左右两部分 左右可以无序  此时时间复杂度为O(n)、O(1)
 */
public class Java_Mother_QuickSort {
    /**
     * 经典快速排序
     */

    /**
     * 随机开始排序
     */
    public static int[] quickSort(int[] arr,int L ,int R){
        //小于区
        int less = L-1;
        //大于区
        int more = R;
        while (L<R){
            if (arr[L]<arr[R]){
                swap(arr,++less,L++);
            }else if (arr[L]>arr[R]){
                swap(arr,L++,--more);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return arr;
//        return new int[]{less+1,more};
    }
    public static int[] swap(int[] arr,int L,int R){
        if (arr[L]<arr[R]){
            int temp = arr[L];
            arr[L]= arr[R];
            arr[R]=temp;
        }
        return arr;
    }
    public static void main(String[] args){
        int[] arr ={1,3,4,5,3,4};
        int[] ints = quickSort(arr, 0, arr.length - 1);
        for(int temp: ints ){
            System.out.println(temp);
        }
        for (int obj:arr){
            System.out.println(obj);
        }
    }

}
